package com.le.medium.class4;

import org.junit.Test;

/**
 * 给定一个数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器， 请返回容器能装多少水
 * 比如，arr = {3，1，2，5，2，4}，根据值画出的直方图就是容器形状，该容器可以装下5格水
 * 再比如，arr = {4，5，1，3，2}，该容器可以装下2格水
 */
public class Problem05_WaterProblem {

    public static int getWater(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int[] leftMax = new int[height.length];
        leftMax[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        int[] rightMax = new int[height.length];
        rightMax[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int res = 0;
        for (int i = 1; i < height.length - 1; i++) {
            res += Math.max(0, Math.min(leftMax[i - 1], rightMax[i + 1]) - height[i]);
        }
        return res;
    }

    public static int getWater2(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int res = 0;
        int leftMax = height[0];
        int rightMax = height[height.length - 1];
        int L = 1;
        int R = height.length - 2;
        while (L <= R) {
            if (leftMax <= rightMax) {
                res += Math.max(0, leftMax - height[L]);
                leftMax = Math.max(leftMax,height[L++]);
            }else {
                res += Math.max(0,rightMax - height[R]);
                rightMax = Math.max(rightMax,height[R--]);
            }
        }
        return res;
    }

    public static int getWater4(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int value = 0;
        int leftMax = arr[0];
        int rightMax = arr[arr.length - 1];
        int l = 1;
        int r = arr.length - 2;
        while (l <= r) {
            if (leftMax <= rightMax) {
                value += Math.max(0, leftMax - arr[l]);
                leftMax = Math.max(leftMax, arr[l++]);
            } else {
                value += Math.max(0, rightMax - arr[r]);
                rightMax = Math.max(rightMax, arr[r--]);
            }
        }
        return value;
    }

    @Test
    public void test() {
        int[] arr = {3, 1, 2, 5, 2, 4};
        int[] arr1 = {4, 5, 1, 3, 2};
        int[] arr2 = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(getWater(arr2));
        System.out.println(getWater2(arr2));
        System.out.println(getWater4(arr2));
    }
}
